/*
The MIT License (MIT)

Copyright (c) 2013 Mike Dapiran, Brian May, Richard Pospesel, and Bert Wierenga

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE.
*/
#pragma once

#include "hhdIEnumerator.hpp"
#include "hhdHashFunctions.hpp"
#include "hhdEqualityFunctions.hpp"
#include "hhdPair.hpp"
#include "hhdVector.hpp"

namespace hhd
{
    /**
    * HashTable implements a simple finite size HashTable which handles collisions using linear probing
    * The hash table doubles in size when it reaches half capacity to avoid
    * collisions.  HashTable assumes that both Key and Value have an assignment operator implemented.
    */

    template<typename Key, typename Value> class HashTable
    {
    public:
        /**
        * Default constructor automagically gets your hash and equality function for the
        * given key.  Initial size of the HashTable is 100.
        */
        HashTable()
            : _load_factor(0.5f)
            , _size(32)
            , _elements(0)
			, _hash(NULL)
			, _equals(NULL)
        {
            _hash = &HashFunctions::primitive_hash<Key>;
            _equals = &EqualityFunctions::equals<Key>;

            _data = new Pair<Key, Value>*[_size];
            memset(_data, 0, sizeof(Pair<Key, Value>*) * _size);
        }

        HashTable(size_t in_size)
            : _load_factor(0.5f)
            , _size(in_size)
            , _elements(0)
        {
            HHD_ASSERT(in_size > 0);

            _hash = &HashFunctions::primitive_hash<Key>;
            _equals = &EqualityFunctions::equals<Key>;

            _data = new Pair<Key, Value>*[_size];
            memset(_data, 0, sizeof(Pair<Key, Value>*) * _size);
        }

		HashTable(const HashTable& other)
			: _load_factor(0.5f)
		{
            _hash = other._hash;
            _equals = other._equals;

            _size = other._size;
            _elements = other._elements;

            _data = new Pair<Key, Value>*[_size];
            for(size_t k = 0; k < _size; k++)
            {
                Pair<Key, Value>* p = other._data[k];
                if(p != NULL)
                {
                    _data[k] = new Pair<Key, Value>(p->first, p->second);
                }
                else
                {
                    _data[k] = NULL;
                }
            }
        }

        HashTable(size_t (*in_hash)(const Key&), bool (*in_equals)(const Key&, const Key&))
            : _load_factor(0.5f)
            , _size(32)
            , _elements(0)
        {
            _hash = in_hash;
            _equals = in_equals;

            _data = new Pair<Key, Value>*[_size];
            memset(_data, 0x00, sizeof(Pair<Key, Value>*) * _size);
        }

        HashTable& operator=(const HashTable& other)
        {
            // first delete memory
            for(size_t k = 0; k < _size; k++)
            {
                if(_data[k] != NULL)
                {
                    delete _data[k];
                }
            }
            delete[] _data;

            _hash = other._hash;
            _equals = other._equals;

            _size = other._size;
            _elements = other._elements;

            _data = new Pair<Key, Value>*[_size];
            for(size_t k = 0; k < _size; k++)
            {
                Pair<Key, Value>* p = other._data[k];
                if(p != NULL)
                {
                    _data[k] = new Pair<Key, Value>(p->first, p->second);
                }
                else
                {
                    _data[k] = NULL;
                }
            }
            return *this;
        }

        ~HashTable()
        {
            for(size_t k = 0; k < _size; k++)
            {
                if(_data[k] != NULL)
                {
                    delete _data[k];
                }
            }
            delete[] _data;
            // delete the enumerators
            for(size_t k = 0; k < _enumerators.size(); k++)
            {
                delete _enumerators[k];
            }

        }

        /**
        * Boolean function to determine if the given Key exists in the HashTable.
        * @param in_key Key to check against.
        * @return True if the key exists, false if it does not.
        */

        bool contains(Key in_key) const
        {
            for(size_t index = _hash(in_key) % _size; _data[index] != NULL; index = (index + 1) % _size)
            {
                if(_equals(_data[index]->first,in_key))
                {
                    return true;
                }
            }
            return false;
        }

        /**
        * Add a Key/Value pair to the HashTable.  Automatically grows the internal array when half
        * capacity is reached.
        * @param in_key The key to add
        * @param in_value The value to add
        * @return True if added successfully, False if the key already exists.
        */

        bool add(Key in_key, Value in_value)
        {
            //resize
            if(_size * _load_factor <= _elements)
            {
                resize();
            }

            //bool key_exists = false;
            size_t index;
            for(index = _hash(in_key) % _size; _data[index] != NULL; index = (index + 1) % _size)
            {
                if(_equals(_data[index]->first, in_key))
                {
                    return false;
                }
            }
            _data[index % _size] = new Pair<Key, Value>(in_key, in_value);
            _elements++;
            return true;
        }

        /**
        * Try to get the value associated with the given key from the HashTable.
        * @param in_key The key to look for.
        * @param out_value Resulting Value is stored here.
        * @return True if we found the Key, false otherwise.
        */

        bool tryGetValue(const Key& in_key, Value& out_value) const
        {
            for(size_t index = _hash(in_key); _data[index % _size]; index++)
            {
                Pair<Key, Value>* p = _data[index % _size];
                if(_equals(p->first, in_key))
                {
                    out_value = p->second;
                    return true;
                }
            }

            return false;
        }

        /**
        * Removes the given key from the HashTable.
        * @param in_key Key to look for and remove.
        * @return True if removed successfully, false if the Key was not in the HashTable.
        */

        bool remove(const Key& in_key)
        {
            // return false if doesn't exist in hash table
            if(!contains(in_key))
            {
                return false;
            }

            // basically we have to redo the hash table now
            Pair<Key, Value>** new_data = new Pair<Key, Value>*[_size];
            memset(new_data, 0, sizeof(Pair<Key, Value>*) * _size);

            for(size_t i = 0; i < _size; i++)
            {
                Pair<Key, Value>* p = _data[i];
                if(p != NULL)
                {
                    if(!_equals(p->first, in_key))
                    {
                        size_t index = _hash(p->first);
                        while(new_data[index % _size] != NULL)
                        {
                            index++;
                        }
                        new_data[index % _size] = p;
                    }
                    else
                    {
                        delete p;
                    }
                }

            }

            delete[] _data;
            _data = new_data;

            _elements--;
            return true;
        }
        /**
        * Subscript operator lets you access an existing Value or set a new one.  If the given
        * Key does not exist in the HashTable, a new Key/Value pair is added and the Value
        * reference is returned.
        */
        Value& operator[](const Key& in_key)
        {
            // first see if we can find the key and return a reference to the value
            size_t index;

            for(index = _hash(in_key); _data[index % _size] != 0; index++)
            {
                Pair<Key, Value>* p = _data[index % _size];
                if(_equals(p->first, in_key))
                {
                    return p->second;
                }
            }

            // if we get here, then we need to add a new key/value pair, se see if we need to resize
            // and update the index
            if(_size * _load_factor <= _elements)
            {
                resize();
                for(index = _hash(in_key); _data[index % _size] != 0; index++);
            }

            // make a new pair
            Pair<Key, Value>* p = new Pair<Key, Value>();
            p->first = in_key;
            _data[index % _size] = p;
            // update elements
            _elements++;
            return p->second;
        }

        template<typename S>
		class HashTableEnumerator : public IEnumerator<S>
        {
            friend class HashTable;
        private:
            HashTableEnumerator(const HashTable& in_table) : _table(in_table), _index(0)
            {
            }
        public:
			virtual ~HashTableEnumerator()
			{

			}

            bool moveNext()
            {
                while(_index < _table._size)
                {
                    if(_table._data[_index] != NULL)
                    {
                        _current = _table._data[_index];
                        _index++;
                        return true;
                    }
                    _index++;

                }
                _current = NULL;
                return false;
            };

            S& current() const
            {
                return *_current;
            };

            void reset()
            {
                _index = 0;
            };

        private:
            S* _current;
            size_t _index;
            const HashTable& _table;
        };

        IEnumerator< Pair< Key, Value > >& getEnumerator()
        {
            HashTableEnumerator<Pair<Key,Value> >* result = new HashTableEnumerator<Pair<Key,Value> >(*this);
            _enumerators.add(result);
            return *result;
        }

        IEnumerator<Pair<Key,Value> >* getNewEnumerator() const
        {
            return new HashTableEnumerator< Pair< Key, Value > >(*this);
        }

        void clear()
        {
            // delete pairs
            for(size_t k = 0; k < _size; k++)
            {
                if(_data[k])
                {
                    delete _data[k];
                    _data[k] = 0;
                }
            }
            // null out pointers
            _elements = 0;
        }

    private:
        void resize()
        {
            size_t new_size = _size * 2;
            Pair<Key, Value>** new_data = new Pair<Key, Value>*[new_size];
            memset(new_data, 0, sizeof(Pair<Key, Value>*) * new_size);
            for(size_t i = 0; i < _size; i++)
            {
                Pair<Key, Value>* p = _data[i];
                if(p != NULL)
                {
                    size_t index = _hash(p->first);
                    while(new_data[index % new_size] != NULL)
                    {
                        index++;
                    }
                    new_data[index % new_size] = p;
                }
            }

            delete[] _data;
            _data = new_data;
            _size = new_size;
        }

        Pair<Key, Value>** _data;
        Vector< HashTableEnumerator< Pair< Key, Value > >* > _enumerators;

        size_t _size;
        size_t _elements;

        // hash function
        uint32_t (*_hash)(const Key&);

        // equals function
        bool (*_equals)(const Key&, const Key&);

        const float _load_factor;

    public:
        /**
        * Returns the number of Key/Value pairs in the HashTable.
        */
        size_t elements()
        {
            return _elements;
        }
    };
}
